package com.foreknow.demo16;

import java.util.Arrays;

/**
 * 插入排序
 * 把n个待排序的元素看成为一个有片表和一个无片表。开始时有序表中只包含1个元素无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素,
 * 将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1大可完成排序过程原始裁组 [4 2 8 9 5 7 6 1 3]
 * 有序表
 * 待排序表
 * 4
 * 2 8 9 5 7 6 1 3
 * 第一轮:2 4
 * 第二轮:2 4 8
 * ceshi
 */
public class Test3 {
    public static void InsertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                } else {
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = { 7, 6, 9, 3, 1, 5, 2, 4 };
        InsertSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
